/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/partition-list
   @Language: C++
   @Datetime: 16-02-09 05:14
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
	/**
	 * @param head: The first node of linked list.
	 * @param x: an integer
	 * @return: a ListNode 
	 */
	ListNode *partition(ListNode *head, int x) {
		// write your code here
		if (head==NULL) return NULL;
		ListNode L(-1), R(-1), *l, *r;
		for(l=&L,r=&R; head; head=head->next)
			if (head->val < x) l=l->next=head;
			else r=r->next=head;
		r->next = NULL;
		l->next = R.next;
		return L.next;
	}
};
